package leetcode.weekly.week335;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import leetcode.helper.tree.TreeNode;

//Solution2Test
public class Solution2 {

	public long kthLargestLevelSum(TreeNode root, int k) {
		List<Long> list = new ArrayList<>();
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			int size = queue.size();
			long sum = 0;
			while(size > 0) {
				TreeNode cur = queue.poll();
				sum += cur.val;
				if(cur.left!=null)
					queue.add(cur.left);
				if(cur.right!=null)
					queue.add(cur.right);
				size--;
			}
			list.add(sum);
		}
		Collections.sort(list);
		if(list.size()<k) {
			return -1;
		}
		return list.get(list.size() - k);
	}

}
